#pragma once

#include <vector>

namespace jianzhi_049
{

class Solution
{
public:
    int nthUglyNumber(int n)
    {
        std::vector<int> ugly(n);
        ugly.front() = 1;
        for (int i = 1, a = 0, b = 0, c = 0; i < n; ++i) {
            int a2 = ugly.at(a) * 2;
            int b3 = ugly.at(b) * 3;
            int c5 = ugly.at(c) * 5;
            ugly.at(i) = std::min(a2, std::min(b3, c5));
            if (a2 == ugly.at(i)) ++a;
            if (b3 == ugly.at(i)) ++b;
            if (c5 == ugly.at(i)) ++c;
        }
        return ugly.back();
    }
};

}  /* namespace jianzhi_049 */
